#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "unordered_map"

using namespace std;
/*HJJ QQ479287006
 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

 

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
 

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：

输入：s = "a", t = "a"
输出："a"
示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*
 * */
//"aaaaaaaaaaaabbbbbcdd"
//"abcdd"
// 浅看了一下 用的map 双指针
//我写错了因为原来理解错了 因为 这个东西不连续他也可以
string minWindow(string s, string t) {
    if (s.size() < t.size())
        return "";
    int count = t.size();

    int tmap[128];

    memset(tmap, -0x1, sizeof(tmap));
    for (int i = 0; i < t.size(); ++i) {
        ++tmap[t[i]];
    }
    for (int i = 0; i < 128; ++i) {
        if (tmap[i] != -1)
            ++tmap[i];
    }


    int ret[2] = {0};
    int minSize = INT_MAX;
    int low = 0;
    int high = 0;
    while (low <= high && low < s.size() && high < s.size()) {
        //说明找到了一个
        if (tmap[s[high]] > 0) {
            count--;
            --tmap[s[high]];//缓存--
        } else if (tmap[s[high]] == 0) {
            //说明找到重复字符串了low y
            if (tmap[s[low]] >= 0) {
                ++tmap[s[low]]; //需要加
                count++;
            }
            low++;
            continue;

        }
        //说明已经找到一个
        if (count == 0) {
            while (tmap[s[low]] == -1 && low <= high && low < s.size())
                low++;

            if (high - low < minSize) {
                minSize = high - low;
                ret[0] = low;
                ret[1] = high;
                if (tmap[s[low]] >= 0) {
                    ++tmap[s[low]];//需要加
                    count++;
                }
                low++;
                high++;
                continue;
            }

        }

        high++;//否则没有达到长度继续后移

    }

    if (minSize > s.size())
        return "";

    return s.substr(ret[0], minSize);
}


string minWindow1(string s, string t) {
    unordered_map<char, int> map_t;//记录t中每个字符出现的次数
    unordered_map<char, int> map_s;//记录s滑动窗口中每个字符出现的次数
    for (auto c : t) {
        map_t[c]++;
    }
    int left = 0;
    int count = 0;
    string res;
    for (int right = 0; right < s.size(); right++) {
        map_s[s[right]]++;
        if (map_s[s[right]] <= map_t[s[right]]) count++;
        //我大致理解了 这边左边肯定是包含所有字符串的 因为这个是left
        while (map_s[s[left]] > map_t[s[left]]) {
            map_s[s[left]]--;
            left++;
        }
        if (count == t.size()) {
            if (res.empty()) res = s.substr(left, right - left + 1);
            else if (right - left + 1 <= res.size()) {
                res = s.substr(left, right - left + 1);
            }
        }
    }
    return res;
}
